import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while (t > 0) {
            t--;
            int n = sc.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

            long[] dp = new long[n + 1];
            List<Long> list = new ArrayList<>();
            for (int i = 1; i < n + 1; i++) {
                dp[i] = Math.max(dp[i - 1] + arr[i - 1], arr[i - 1]);
                if (i > 1 && dp[i] == arr[i - 1]) {
                    list.add(dp[i - 1]);
                }
            }

            list.add(dp[n]);

            int count = 1;
            long sum = 0;
            for (long num : list) {
                sum += num * count;
                count++;
            }
            System.out.println(sum);
        }

        sc.close();
    }
}
